class Solution {
public:
    string minWindow(string s, string t) {
        int s_len = s.size(), t_len = t.size();
        if (t_len > s_len)
            return "";

        int s_hash[128] = {0};
        int t_hash[128] = {0};
        for (auto e : t)
            t_hash[e]++;

        //cnt用来记录s_hash中有效字符的总个数
        //当cnt的值等于t的长度，就说明[left, right]字符串就覆盖了t字符串
        //之后，就不断缩小窗口，直到窗口内的字符串无法覆盖t
        //缩小的同时更新返回字符串的起始位置和长度
        //最后再得到返回的字符串
        int len = INT_MAX, cnt = 0, begin = 0;  
        for (int left = 0, right = 0; right < s_len; right++)
        {
            s_hash[s[right]]++;
            if (t_hash[s[right]] >= s_hash[s[right]])
                cnt++;

            while (cnt == t_len)
            {
                int tmp_len = right - left + 1;
                if (tmp_len < len)
                {
                    len = tmp_len;
                    begin = left;
                }

                if (s_hash[s[left]] <= t_hash[s[left]])
                    cnt--;
                s_hash[s[left++]]--;
            }
        }

        return len == INT_MAX ? "" : s.substr(begin, len);
    }
};